package _03_栈;

public class _844_比较含退格的字符串 {

    public static void main(String[] args) {

        _844_比较含退格的字符串 v = new _844_比较含退格的字符串();
        System.out.println(v.backspaceCompare("bbbextm", "bbb#extm"));
    }

    // 双指针写法
    public boolean backspaceCompare(String s, String t) {
        int right1 = s.length() - 1;
        int right2 = t.length() - 1;
        int skip1 = 0;
        int skip2 = 0;
        while (right1 >= 0 || right2 >= 0) {
            // 计算结尾的#
            while (right1 >= 0 && s.charAt(right1) == '#') {
                right1--;
                skip1++;
            }
            while (right2 >= 0 && t.charAt(right2) == '#') {
                right2--;
                skip2++;
            }
            boolean isLastLetters = false;
            // 如果是字母
            while (right1 >= 0 && skip1 > 0) {
                right1--;
                skip1--;
                // 判断下一个字符是否为 #
                if (right1 >= 0 && s.charAt(right1) == '#') {
                    isLastLetters = true;
                    break;
                }
            }
            // 消减字母
            while (right2 >= 0 && skip2 > 0) {
                right2--;
                skip2--;
                if (right2 >= 0 && t.charAt(right2) == '#') {
                    isLastLetters = true;
                    break;
                }
            }
            if (isLastLetters) continue;
            ;
            // 能执行到下面。那么必定是字符, 要不然就是空字符
            char cur1 = right1 >= 0 ? s.charAt(right1--) : ' ';
            char cur2 = right2 >= 0 ? t.charAt(right2--) : ' ';
            if (cur1 != cur2) return false;
        }
        return true;
    }


    public boolean backspaceCompare1(String s, String t) {
        return build(s).equals(build(t));
    }

    // 重构字符串，利用栈思想，如果遇到#就将栈顶元素弹出，非#压入栈
    public String build(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur != '#') {
                builder.append(cur);
            } else if (builder.length() > 0) {
                builder.deleteCharAt(builder.length() - 1);
            }
        }
        return builder.toString();
    }
}
